package com.jn.algorithm.day007.question22;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 江南大学1033190417
 * @date 2022/4/21 17:09
 */
public class Solution {

    /*
       暴力解法
       先排列出所有的组合，在去除不符合的
     */
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<String>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    //递归组合所有情况
    public void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (valid(current)) {
                result.add(new String(current));
            }
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }

    //判断是否合法
    public boolean valid(char[] current) {
        int balance = 0;
        for (char c : current) {
            if (c == '(') {
                ++balance;
            } else {
                --balance;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }


    public List<String> myGenerateParenthesis(int n) {
        List<String> res = new ArrayList<>();

        myGenerateAll(new char[2 * n], 0, res);

        return res;
    }

    public void myGenerateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {//递归结束条件
            if (isOK(current)) {
                result.add(new String(current));
            }
        } else {
            current[pos] = '(';
            myGenerateAll(current, pos + 1, result);
            current[pos] = ')';
            myGenerateAll(current, pos + 1, result);
        }

    }

    //判断字符串是否符合
    public boolean isOK(char[] chars) {
        int balance = 0;
        for (char c : chars) {
            if (c == '(') {
                ++balance;
            } else {
                --balance;
            }
            if (balance < 0) {
                return false;
            }
        }
        return balance == 0;
    }


    //回溯法
    /*
       思路：
           方法1还有改进的余地，我们只需在当前序列仍然保持有效使才添加'('或')'
           而不是像方法1每次都添加
           如果左括号数量<=n(一半)，那么可以放一个左括号，如果右括号小于左括号，可以放一个右括号
     */

    public List<String> myGenerateParenthesis2(int n) {
        List<String> res = new ArrayList<>();
        backTrack(res, new StringBuilder(), 0, 0, n);
        return res;
    }

    /**
     * @param res   返回结果
     * @param cur   当前串
     * @param open  左括号数量
     * @param close 右括号数量
     * @param max   长度最大值
     */
    public void backTrack(List<String> res, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {//因为一定是正确的，直接添加到结果集即可
            res.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append('(');
            backTrack(res, cur, open + 1, close, max);
            //回溯
            cur.deleteCharAt(cur.length() - 1);
        }
        if (open > close) {
            cur.append(')');
            backTrack(res, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.myGenerateParenthesis2(3));
    }
}
